In colour printing environments the total uncompressed size of a generated pixel image is often large and it is advantageous to avoid storing the entire image uncompressed. Such pixel images are typically generated in raster, band, or block order. In particular data corresponding to pixels, scanlines, groups of scanlines, or tiles, is emitted in a stream from a raster image processor that has as input an object graphic description of the page to be printed. Data to be compressed is often pixel colour values, but could be any other image information, referred to hereafter as image data.
Image data can be compressed either with or without loss of information. Many schemes have been proposed for lossless image compression; some of them are based on entropy encoding, while other methods are dictionary-based. In the latter, raw data is mapped onto smaller-size codes. The codes and the mapping are stored in a structure known as a dictionary.
When used in image compression, a palette, which is one example of a dictionary, is a mapping between distinct image data values (or image values) that are used within the image and shorter encoded values known as palette values. When the number of distinct values to be encoded is small, a palette-based method works well, as both the palette and the palette values replacing the original data are small. The palette can contain mappings for the whole image or only for parts of that image. In the latter case, the palette is known in the art as a local palette or a sub-palette. Palette reordering is a technique known in the art as a method for improving compression. Encoding using the reordered palette tends to yield a better compression ratio.
When storing encoded data, it is desirable that its binary (or other) representation is as small as possible and one way to achieve that is by writing each encoded value with the smallest possible number of bits. The problem with such an approach is that during decoding it might be difficult to recognise where one encoded value ends and another one begins. Hence, very often palette values of fixed length, which is determined by the overall size of the palette, are used to encode the data. When variable length codes are used, one way of solving ambiguity during decoding is to ensure that no one code is a prefix of another. Huffman codes are an example of such encoding.
Other schemes vary the length of encoded values in the bit-stream by inserting length information in the compressed bitstream to guide decompression. U.S. Pat. No. 6,225,922 B1 uses variable length encoding with length flags followed by the actual length indicating that the encoded data values from that point onwards should be read with that length. U.S. Pat. No. 5,825,830 A provides rules for automatically either increasing or decreasing the binary field length for encoding the next data value based on the current field length and the encoded data value. While more sophisticated in the way the length of the current value is determined and partially automated in determining the field length, it also inserts length information into the bit stream, an approach which not only increases the length of the final encoding, but also complicates the decompression process.